SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Threaded binary tree</title>

</head>

Threaded binary tree

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Computing" title="Computing">computing</a>, a threaded binary tree is a <a href="Binary_tree" title="Binary tree">binary tree</a> variant that facilitates <a href="Tree_traversal" title="Tree traversal">traversal</a> in a particular order.

An entire binary search tree can be easily traversed in order of the main key but given only a <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> to a <a href="Node_(computer_science)" title="Node (computer science)">node</a>, finding the node which comes next may be slow or impossible. For example, leaf nodes by definition have no descendants, so given only a pointer to a leaf node no other node can be reached. A threaded tree adds extra information in some or all nodes, so that for any given single node the "next" node can be found quickly, allowing tree traversal without recursion and the extra storage (proportional to the tree's depth) that recursion requires.

<div class="mw-heading mw-heading2"><h2 id="Threading">Threading</h2></div>

"A binary tree is threaded by making all right child pointers that would normally be null point to the in-order successor of the node (if it exists), and all left child pointers that would normally be null point to the in-order predecessor of the node."<a href="#cite_note-1">[1]</a>

</blockquote>

This assumes the traversal order is the same as <a href="In-order_traversal" class="mw-redirect" title="In-order traversal">in-order</a> traversal of the tree. However, pointers can instead (or in addition) be added to tree nodes, rather than replacing. <a href="Linked_lists" class="mw-redirect" title="Linked lists">Linked lists</a> thus defined are also commonly called "threads", and can be used to enable traversal in any order(s) desired. For example, a tree whose nodes represent information about people might be sorted by name, but have extra threads allowing quick traversal in order of birth date, weight, or any other known characteristic.

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

Trees, including (but not limited to) <a href="Binary_search_tree" title="Binary search tree">binary search trees</a>, can be used to store items in a particular order, such as the value of some property stored in each node, often called a <a href="Key_value" class="mw-redirect" title="Key value">key</a>. One useful operation on such a tree is traversal: visiting all the items in order of the key.

A simple recursive traversal algorithm that visits each node of a <a href="Binary_search_tree" title="Binary search tree">binary search tree</a> is the following. Assume t is a pointer to a node, or nil. "Visiting" t can mean performing any action on the node t or its contents.

/* start https://en.wikipedia.org/ */

.mw-parser-output .framebox-container{margin-bottom:1.25em}.mw-parser-output .framebox-header{height:8px;margin:0;border:0;padding:0;font-size:1px}.mw-parser-output .framebox-inner{padding:5px;font-size:85%}

/* end https://en.wikipedia.org/ */

</style>

Algorithm traverse(t):

<ul><li>Input: a pointer t to a node (or nil)</li>

<li>If t = nil, return.</li>

<li>Else:

<ul><li>traverse(left-child(t))</li>

<li>Visit t</li>

<li>traverse(right-child(t))</li></ul></li></ul>

</div></div>

</div>

One problem with this algorithm is that, because of its recursion, it uses stack space proportional to the height of a tree. If the tree is fairly balanced, this amounts to O(log n) space for a tree containing n elements. In the worst case, when the tree takes the form of a <a href="Path_graph" title="Path graph">chain</a>, the height of the tree is n so the algorithm takes O(n) space. A second problem is that all traversals must begin at the root when nodes have pointers only to their children. It is common to have a pointer to a particular node, but that is not sufficient to get back to the rest of the tree unless extra information is added, such as thread pointers.

In this approach, it may not be possible to tell whether the left and/or right pointers in a given node actually point to children, or are a consequence of threading. If the distinction is necessary, adding a single bit to each node is enough to record it.

In a 1968 textbook, <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a> asked whether a non-recursive algorithm for in-order traversal exists, that uses no stack and leaves the tree unmodified.<a href="#cite_note-2">[2]</a> One of the solutions to this problem is tree threading, presented by Joseph M. Morris in 1979.<a href="#cite_note-3">[3]</a><a href="#cite_note-4">[4]</a>

In the 1969 follow-up edition,<a href="#cite_note-5">[5]</a> Knuth attributed the threaded tree representation to <a href="Alan_Perlis" title="Alan Perlis">Perlis</a> and Thornton (1960).<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Relation_to_parent_pointers">Relation to parent pointers</h3></div>

Another way to achieve similar goals is to include a pointer in every node, to that node's parent node. Given that, the "next" node can always be reached, "right" pointers are still null whenever there are no right children. To find the "next" node from a node whose right pointer is null, walk up through "parent" pointers until reaching a node whose right pointer is not null, and is not the child you just came up from. That node is the "next" node, and after it come its descendants on the right.

It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, although it is slower. To see this, consider a node k with right child r. Then the left pointer of r must be either a child or a thread back to k. In the case that r has a left child, that left child must in turn have either a left child of its own or a thread back to k, and so on for all successive left children. So by following the chain of left pointers from r, we will eventually find a thread pointing back to k. The situation is symmetrically similar when q is the left child of p—we can follow q's right children to a thread pointing ahead to p.

In <a href="Python_(programming_language)" title="Python (programming language)">Python</a>:<div class="mw-highlight mw-highlight-lang-python mw-content-ltr" dir="ltr"><pre>def parent(node):

if node is node.tree.root:

return None

x = node

y = node

while True:

if is_thread(y):

p = y.right

if p is None or p.left is not node:

p = x

while not is_thread(p.left):

p = p.left

return p

elif is_thread(x):

p = x.left

if p is None or p.right is not node:

p = y

p = p.right

return p

x = x.left

y = y.right

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Types">Types</h2></div>

<ol><li>Single threaded: each node is threaded towards either the in-order predecessor or successor (left or right).</li>

<li>Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right).</li></ol>

<div class="mw-heading mw-heading2"><h2 id="The_array_of_in-order_traversal">The array of in-order traversal</h2></div>

Threads are reference to the predecessors and successors of the node according to an inorder traversal.

<a href="Inorder" class="mw-redirect" title="Inorder">In-order</a> traversal of the threaded tree is <code>A,B,C,D,E,F,G,H,I</code>, the predecessor of <code>E</code> is <code>D</code>, the successor of <code>E</code> is <code>F</code>.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Let's make the Threaded Binary tree out of a normal binary tree:

The <a href="Inorder" class="mw-redirect" title="Inorder">in-order</a> traversal for the above tree is — D B A E C. So, the respective Threaded Binary tree will be --

<div class="mw-heading mw-heading2"><h2 id="Null_links">Null links</h2></div>

In an m-way threaded binary tree with n nodes, there are n×m − (n−1) void links.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1988, p. 175. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-16116-8</bdi>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKnuth1968" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, D.E.</a> (1968). Fundamental Algorithms. The Art of Computer Programming. Vol. 1 (1st ed.). Reading/MA: Addison Wesley.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFMorris1979" class="citation journal cs1">Morris, Joseph H. (1979). "Traversing binary trees simply and cheaply". <a href="Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a>. 9 (5). <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2879%2990068-1">10.1016/0020-0190(79)90068-1</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFMatetiManghirmalani1988" class="citation journal cs1">Mateti, Prabhaker; Manghirmalani, Ravi (1988). "Morris' tree traversal algorithm reconsidered". Science of Computer Programming. 11: 29–43. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0167-6423%2888%2990063-9">10.1016/0167-6423(88)90063-9</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFKnuth1969" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, D.E.</a> (1969). Fundamental Algorithms. The Art of Computer Programming. Vol. 1 (2 ed.). Addison Wesley.</cite> Hre: Sect.2.3.1 "Traversing Binary Trees".

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFPerlisThornton1960" class="citation journal cs1">Perlis, Alan Jay; Thornton, C. (Apr 1960). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F367177.367202">"Symbol manipulation by threaded lists"</a>. Communications of the ACM. 3 (4): 195–204. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F367177.367202">10.1145/367177.367202</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://adtinfo.org/libavl.html/Threaded-Binary-Search-Trees.html">GNU libavl 2.0.2, Section on threaded binary search trees</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-21" href="https://en.wikipedia.org/wiki/?title=Threaded_binary_tree&oldid=1276876627">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>